home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Practical Algorithms for Image Analysis
/
Practical Algorithms for Image Analysis.iso
/
CH_5.7
/
XSGLL
/
SGL_TO_P.C
< prev
next >
Wrap
C/C++ Source or Header
|
1999-09-11
|
11KB
|
345 lines
/*
* sgl_to_p.c
*
* Practical Algorithms for Image Analysis
*
* Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
*/
/*
* SGL_TO_POLY
*
* routines to construct ordered, cyclic array of vertices, given
* a segm group list containing elements in the order of increasing dij
*/
#include <stdio.h>
#include <math.h>
#include "lldef.h"
#include "xsgll.h"
#undef DEBUG_VA
#undef DEBUG_MERGE
/* globals */
extern int MERGE;
/*
* merge two successive ("current" and "next") segments
* sharing a common vertex and delete "current" segment from list
*/
void
merge_segm (segm, list, cSegm, nSegm, nva, MergeDirn)
struct Segm *segm;
struct linklist *list;
struct Segmtype *cSegm, *nSegm;
int *nva;
Boolean MergeDirn;
{
if (MergeDirn == Forward) {
(segm + nSegm->segm_ind)->ptO.x = (segm + cSegm->segm_ind)->ptO.x;
(segm + nSegm->segm_ind)->ptO.y = (segm + cSegm->segm_ind)->ptO.y;
}
else {
(segm + nSegm->segm_ind)->ptF.x = (segm + cSegm->segm_ind)->ptF.x;
(segm + nSegm->segm_ind)->ptF.y = (segm + cSegm->segm_ind)->ptF.y;
}
llprevious (list);
lldelete (list);
*nva -= 2;
}
/*
* swap two points
*/
Boolean
swap_pts (pt1, pt2)
struct spoint *pt1, *pt2;
{
struct spoint temp_pt;
temp_pt.x = pt2->x;
temp_pt.y = pt2->y;
pt2->x = pt1->x;
pt2->y = pt1->y;
pt1->x = temp_pt.x;
pt1->y = temp_pt.y;
return (True);
}
/*
* construct an ordered, cyclic array of vertices from the endpoints
* of the segments in a given SGL in which these segments are stored
* in order of increasing dij;
* the sense of the resulting closed polygon is determined by the
* orientation of the reference segment at the top of the list;
* by construction (see sall.c), all segments in a given SGL have
* similar slopes (not necessarily of the same sign, as in the case
* where segments which are nearly parallel with the x-axis but point
* into different quadrants);
*
* establish a reference orientation as follows:
* let the vector vr:=( r_delx, r_dely ) define the reference segment;
* the slope m of the reference segment is given by m=r_dely/r_delx;
* let the vector vr_perp define the line segment perpendicular to vr
* with length equal to that of vr; since the slope of the perpendicular
* line segment, m_perp, is given by m_perp=-1.0/m=r_delx/(-r_dely),
* one has: xf_perp = xo - r_dely and yf_perp = yo + r_delx; the sign of
* the cross product r_cof:=(vr x vr_perp) is taken to define the
* reference orientation (note: this reference cross product is by
* construction non-zero!);
* the orientation of all other segments in the SGL, represented by the
* vector vs:=( (ptF.x-ptO.x), (ptF.y-ptO.y) ), is compared with the
* reference orientation as follows:
* construct a line segment of slope m_perp(!) containing ptO=(c_xo, c_yo)
* of the current segment; since the length of this line segment is
* immaterial, define vs_perp by choosing the following coordinates
* for the endpoint: c_xf_perp = c_xo - r_dely, c_yf_perp = c_yo + r_delx;
* finally, evaluate the cross product (vs x vs_perp) and compare its
* sign to the reference orientation: swap enpoints of current segment
* if indicated;
*/
double
construct_va (segm, list, nva, va)
struct Segm *segm;
struct linklist *list;
int *nva;
struct spoint *va;
{
struct Segmtype *rSegm, *cSegm, *nSegm;
long r_cof, c_cof;
long xo, yo, xf, yf;
long r_delx, r_dely, c_delx, c_dely;
long xc_o, yc_o, xc_f, yc_f;
long xn_o, yn_o, xn_f, yn_f;
int sr_cof, sc_cof;
double av_azimuth;
double r_slp, c_slp, av_slope, dnull = 0.0;
int sr_slp, sc_slp;
int i, n, nn;
Boolean SwapStat;
/*
* scan SGL (assumed to contain segments in increasing order of dij):
* inspect each segment and bring all segments into the same orientation,
* arbitrarily chosen to be that of the segment at the top of the list
*/
llhead (list);
rSegm = (struct Segmtype *) list->clp->item;
xo = (long) (segm + rSegm->segm_ind)->ptO.x;
yo = (long) (segm + rSegm->segm_ind)->ptO.y;
xf = (long) (segm + rSegm->segm_ind)->ptF.x;
yf = (long) (segm + rSegm->segm_ind)->ptF.y;
r_delx = xf - xo;
r_dely = yf - yo;
/*
* reference orientation
*/
r_cof = (-r_dely) * r_dely - (r_delx * r_delx);
sr_cof = SIGN (r_cof);
if ((sr_cof == 0)) {
printf ("\n...vanishing cross product for ref Segm: ");
printf ("unknown condition!!\n");
return (dnull);
}
#ifdef DEBUG_VA
printf ("\n\n...end points of reference segment:\n");
printf (" ptO.x = %d, ptO.y = %d\n",
(segm + rSegm->segm_ind)->ptO.x, (segm + rSegm->segm_ind)->ptO.y);
printf (" ptF.x = %d, ptF.y = %d\n",
(segm + rSegm->segm_ind)->ptF.x, (segm + rSegm->segm_ind)->ptF.y);
printf (" sign( reference cross_prd ) = %d\n", sr_cof);
#endif
while (llnext (list) == True) {
SwapStat = False;
cSegm = (struct Segmtype *) list->clp->item;
xo = (long) (segm + cSegm->segm_ind)->ptO.x;
yo = (long) (segm + cSegm->segm_ind)->ptO.y;
xf = (long) (segm + cSegm->segm_ind)->ptF.x;
yf = (long) (segm + cSegm->segm_ind)->ptF.y;
c_delx = xf - xo;
c_dely = yf - yo;
c_cof = (-r_dely) * c_dely - r_delx * c_delx;
sc_cof = SIGN (c_cof);
if ((sc_cof == 0)) {
printf ("\n...vanishing cross product for cur Segm: ");
printf ("unknown condition!!\n");
return (dnull);
}
#ifdef DEBUG_VA
printf ("\n...current end points (prior to swap):\n");
printf (" ptO.x = %d, ptO.y = %d\n",
(segm + cSegm->segm_ind)->ptO.x, (segm + cSegm->segm_ind)->ptO.y);
printf (" ptF.x = %d, ptF.y = %d\n",
(segm + cSegm->segm_ind)->ptF.x, (segm + cSegm->segm_ind)->ptF.y);
printf (" sign( current cross_prd ) = %d\n", sc_cof);
#endif
if (sc_cof != sr_cof)
SwapStat = swap_pts (&((segm + cSegm->segm_ind)->ptO),
&((segm + cSegm->segm_ind)->ptF));
#ifdef DEBUG_VA
if (SwapStat == True) {
printf ("...end points swapped:\n");
printf (" ptO.x = %d, ptO.y = %d\n",
(segm + cSegm->segm_ind)->ptO.x,
(segm + cSegm->segm_ind)->ptO.y);
printf (" ptF.x = %d, ptF.y = %d\n",
(segm + cSegm->segm_ind)->ptF.x,
(segm + cSegm->segm_ind)->ptF.y);
}
#endif
}
/*
* now that all segm in SGL have the same orientation, merge
* segments sharing a common vertex; that is, replace two successive
* segments {(ptO1.x, ptO1.y), (ptF1.x, ptF1.y)} and
* {(ptO2.x, ptO2.y), (ptF2.x, ptF2.y)} sharing the vertex
* (ptF1.x, ptF1.y) = (ptO2.x, ptO2.y) or the vertex
* (ptO1.x, ptO1.y) = (ptF2.x, ptF2.y) by the new
* segment {(ptO1.x, ptO1.y), (ptF2.x, ptF2.y)}; this is equivalent
* to removing "interior" points from the polygon of segment
* endpoints to be constructed below;
* given that each SGL contains elements in the order of increasing dij
* the search for matching vertices can be restricted to pairs of
* successive sgements in the list;
*/
if (MERGE == 1) {
llhead (list); /* search for shared vertices */
cSegm = (struct Segmtype *) list->clp->item;
while (llnext (list) == True) {
xc_o = (long) (segm + cSegm->segm_ind)->ptO.x;
yc_o = (long) (segm + cSegm->segm_ind)->ptO.y;
xc_f = (long) (segm + cSegm->segm_ind)->ptF.x;
yc_f = (long) (segm + cSegm->segm_ind)->ptF.y;
nSegm = (struct Segmtype *) list->clp->item;
xn_o = (long) (segm + nSegm->segm_ind)->ptO.x;
yn_o = (long) (segm + nSegm->segm_ind)->ptO.y;
xn_f = (long) (segm + nSegm->segm_ind)->ptF.x;
yn_f = (long) (segm + nSegm->segm_ind)->ptF.y;
#ifdef DEBUG_MERGE
printf ("\n");
printf ("...(xc_o,yc_o): (%ld, %ld)", xc_o, yc_o);
printf ("...(xc_f,yc_f): (%ld, %ld)\n", xc_f, yc_f);
printf ("...(xn_o,yn_o): (%ld, %ld)", xn_o, yn_o);
printf ("...(xn_f,yn_f): (%ld, %ld)\n", xn_f, yn_f);
#endif
if ((xc_f == xn_o) && (yc_f == yn_o)) {
#ifdef DEBUG_MERGE
printf ("\n...shared vertex found: ");
printf (" (%ld, %ld)", xc_f, yc_f);
printf (" -> merge Forward\n");
#endif
merge_segm (segm, list, cSegm,
nSegm, nva, Forward);
}
else if ((xc_o == xn_f) && (yc_o == yn_f)) {
#ifdef DEBUG_MERGE
printf ("\n...shared vertex found: ");
printf (" (%ld, %ld)", xc_f, yc_f);
printf (" -> merge Reverse\n");
#endif
merge_segm (segm, list, cSegm,
nSegm, nva, Reverse);
}
cSegm = nSegm;
}
}
/*
* construct an ordered, cyclic vertex array from the segm endpoints;
* in same pass through list, compute the average value of segm slopes;
* recall that atan() returns a value in [-PI/2, PI/2];
*/
n = *nva - 1; /* last array index */
nn = *nva - 2;
llhead (list);
rSegm = (struct Segmtype *) list->clp->item;
r_slp = (double) fslope ((segm + rSegm->segm_ind)->ptO,
(segm + rSegm->segm_ind)->ptF);
if ((sr_slp = SIGN (r_slp)) == 0)
sr_slp = 1;
/* close polygon: first & last vertices identical */
(va + n)->x = (segm + rSegm->segm_ind)->ptO.x;
(va + n)->y = (segm + rSegm->segm_ind)->ptO.y;
av_azimuth = av_slope = 0.0;
i = 0;
do {
cSegm = (struct Segmtype *) list->clp->item;
(va + i)->x = (segm + cSegm->segm_ind)->ptO.x;
(va + i)->y = (segm + cSegm->segm_ind)->ptO.y;
(va + nn - i)->x = (segm + cSegm->segm_ind)->ptF.x;
(va + nn - i)->y = (segm + cSegm->segm_ind)->ptF.y;
c_slp = (double) fslope ((segm + cSegm->segm_ind)->ptO,
(segm + cSegm->segm_ind)->ptF);
if ((sc_slp = SIGN (c_slp)) == 0)
sc_slp = 1;
if (sc_slp == sr_slp)
av_azimuth += atan (c_slp);
else {
xo = (long) (segm + cSegm->segm_ind)->ptO.x;
yo = (long) (segm + cSegm->segm_ind)->ptO.y;
xf = (long) (segm + cSegm->segm_ind)->ptF.x;
yf = (long) (segm + cSegm->segm_ind)->ptF.y;
c_delx = xf - xo;
c_dely = yf - yo;
if (SIGN (r_dely) != SIGN (c_dely)) /* horizontal */
av_azimuth += atan (c_slp);
else if (SIGN (r_delx) != SIGN (c_delx)) { /* vertical */
if (sc_slp < 0)
av_azimuth += (PI + atan (c_slp));
else if (sc_slp > 0)
av_azimuth += (-PI + atan (c_slp));
}
}
i++;
} while (llnext (list) == True);
av_azimuth /= (double) list->listlength;
av_slope = tan (av_azimuth);
return (av_slope);
}